import java.util.*;

/**
 * 面试题 16.25. LRU缓存
 * https://leetcode-cn.com/problems/lru-cache-lcci/
 */
public class Solutions_mianshi_16_25 {
    public static void main(String[] args) {
//        LRUCache3 cache = new LRUCache3(2);
        LRUCache4 cache = new LRUCache4(2);

        cache.put(1, 1);
        cache.put(2, 2);
        int res1 = cache.get(1);  // output: 1
        System.out.println(res1);
        cache.put(3, 3);  // 该操作会使得密钥 2 作废
        int res2 = cache.get(2);  // output: -1（未找到）
        System.out.println(res2);
        cache.put(4, 4);  // 该操作会使得密钥 1 作废
        int res3 = cache.get(1);    // output: -1
        System.out.println(res3);
        int res4 = cache.get(3);  // output: 3
        System.out.println(res4);
        int res5 = cache.get(4);       // 返回  4
        System.out.println(res5);
    }
}

/**
 * 解法二：哈希表 + 双向链表
 * 解题思路：
 * 1. 创建双向链表，链表结点可以获取到前驱结点与后继结点
 * 2. 哈希表用于通过 key 查找到链表结点，并将结点移动到链表的头结点（保证链表前面的结点都是频繁使用的）
 * 3. 当链表大小大于 capacity 时，移除链表尾结点
 * 4. get() 操作时，若 key 存在，则将 key 对应的链表结点移动到链表头部，最终返回 key
 * 5. put() 操作时，若 key 存在，则删除 key 对应的结点，并在链表头部新增一个结点
 *                若 key 不存在，则在链表头部新增一个结点，并记录到 map 中
 */
class LRUCache4 {
    // 双向链表类
    class MyLinkedNode {
        int key;
        int val;
        MyLinkedNode prev;
        MyLinkedNode next;

        public MyLinkedNode() {

        }

        public MyLinkedNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    // 缓存容量
    int capacity;
    // 链表大小
    int size;
    // 哈希表记录 key 所对应的双向链表结点
    Map<Integer, MyLinkedNode> map;
    // 为方便操作，设置虚拟头结点和尾结点
    MyLinkedNode head, tail;

    public LRUCache4(int capacity) {
        this.capacity = capacity;
        size = 0;
        map = new HashMap<>();
        head = new MyLinkedNode();
        tail = new MyLinkedNode();
        // 虚拟头尾结点关联
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        MyLinkedNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 移动到链表头部
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        MyLinkedNode node = map.get(key);
        if (node != null) {
            // 结点已存在，更新值，移动到链表头部
            node.val = value;
            moveToHead(node);
        } else {
            // 链表头部新增结点
            MyLinkedNode newNode = new MyLinkedNode(key, value);
            size++;
            map.put(key, newNode);
            addNodeToHead(newNode);
            if (size > capacity) {
                // 已缓存结点数量 > 缓存容量时，移除久未使用的结点，即链表尾部的元素，即虚拟尾结点的前驱结点
                MyLinkedNode deleteNode = tail.prev;
                removeNode(deleteNode);
                // map 中移除该键
                map.remove(deleteNode.key);
                // 同时双向链表的实际长度减 1
                --size;
            }
        }
    }

    /**
     * 删除结点
     * 要删除结点的前驱结点的后继结点指向要删除结点的后继结点
     * 要删除结点的后继结点的前驱结点指向删除结点的前驱结点
     */
    public void removeNode(MyLinkedNode node) {
        // 获取到要删除结点的前驱结点和后继结点
        MyLinkedNode curPrev = node.prev;
        MyLinkedNode curNext = node.next;
        curPrev.next = curNext;
        curNext.prev = curPrev;
    }

    /**
     * 添加结点到虚拟头结点的后继结点
     * 1. 获取到原本虚拟头结点的后继结点 old
     * 2. old 结点的前驱结点指向新结点
     * 3. 新结点的后继结点指向 old 结点
     * 3. 虚拟头结点的后继节点指向新结点
     * 4. 新结点的前驱结点指向虚拟头结点
     */
    public void addNodeToHead(MyLinkedNode node) {
        // 获取到头结点的下一结点
        MyLinkedNode temp = head.next;
        node.next = temp;
        node.prev = head;
        head.next = node;
        temp.prev = node;
    }

    /**
     * 移动结点到头结点
     * 1. 删除结点
     * 2. 添加结点到头结点
     */
    public void moveToHead(MyLinkedNode node) {
        removeNode(node);
        addNodeToHead(node);
    }
}

/**
 * 解法一：LinkedHashMap 实现（35ms）
 */
class LRUCache3 extends LinkedHashMap<Integer, Integer> {
    // 缓存容量
    int capacity;

    public LRUCache3(int capacity) {
        // 调用父类构造函数
        //     public LinkedHashMap(int initialCapacity,
        //                         float loadFactor,
        //                         boolean accessOrder) {
        //        super(initialCapacity, loadFactor);
        //        this.accessOrder = accessOrder;}
        //
        // 如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序
        // 如果accessOrder为flase的话，则按插入顺序来遍历
        // LinkedHashMap 初始容量为 capacity，当 map 中元素达到 capacity * 0.75 时，map 大小翻倍
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        // 调用父类的方法，给定默认值 -1
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        // 调用父类的方法
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // put 操作后，进入方法
        // 若 return true，便移除 map 中最老的键和值
        // 定义规则：超过缓存容量时，移除 map 中最老的键和值
        return size() > capacity;
    }
}
